#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
# -*- mode: python -*-

from __future__ import print_function
from __future__ import absolute_import
from __future__ import division

CHARS = ';', '<', '>', 'a'
TOKENS = '$', ';', '<', '>', 'ID'
s0 = ((';',2), ('<',3), ('>',1), ('a',4)), ()
s1 = (('>',5),), ('>',)
s2 = (), (';',)
s3 = (), ('<',)
s4 = (), ('ID',)
s5 = (), ('>>',)
STATES = s0, s1, s2, s3, s4, s5
del s0, s1, s2, s3, s4, s5

def move(s, c):
    for sym, target in STATES[s][0]:
        if sym == c:
            return target
    return None

def accept_set(s_p, s_s):
    ts = set(('<', '>'))
    ts = set(('<', '>>'))
    ts = set(('ID', '>>'))
    ts = set(('<', 'ID'))
    ts = set(('ID', '<', '>>'))
    ts &= set(STATES[s_s][1])
    return tuple(sorted(ts))

profile_map = dict()

# <-
def less_by_identity(a, b):
    return False

# -<
def less_by_length(a, b):
    return False

# -s
def prefer_shorter(a, b):
    return False

# -~
def prefer_longer(a, b):
    if a is None:
        return False
    if b is None:
        return False
    return a == b

def check_shorter_token(t_s, T_l):
    for t in T_l:
        if not less_by_length(t, t_s) and \
           not prefer_shorter(t, t_s):
            return False
    return True

def check_longer_token(t_l, T_s):
    for t in T_s:
        if not less_by_length(t, t_l) and \
           not prefer_longer(t, t_l):
            return False
    return True

def choose_token_by_identity(T_l):
    ts = []
    for t_l in T_l:
        for t in T_l:
            if t != t_l and not less_by_identity(t, t_l):
                break
        else:
            ts.append(t_l)
    if len(ts) == 1:
        return ts[0]
    else:
        return None

def choose_longer_token(T_s, T_l):
    t_l = choose_token_by_identity(T_l)
    if t_l is None:
        return None
    if check_longer_token(t_l, T_s):
        return t_l
    return None

def report_conflict(s_p, s_s2, T_s, t_s, T_l):
    args = s_p, s_s2, T_s, t_s, T_l
    print(' ' * indent + '*** conflict: {}'.format(args))

indent = 0
scanner_accept = dict()

def resolve(s_p, s_s, T_s, t_s):
    global indent
    args = s_p, s_s, T_s, t_s
    print(' ' * indent + 'resolve: {}'.format(args))
    indent += 2
    for char in CHARS:
        s_s2 = move(s_s, char)
        if s_s2 is None:
            continue
        print(' ' * indent + 'move: {}'.format((s_s, char, s_s2)))
        indent += 2
        T_l = accept_set(s_p, s_s2)
        profile = T_s, t_s, T_l
        entry = profile_map.get(profile)
        if entry is None:
            entry = set()
            profile_map[profile] = entry
        if s_s2 not in entry:
            if not T_l or (t_s is not None and check_shorter_token(t_s, T_l)):
                t_l = t_s
            else:
                t_l = choose_longer_token(T_s, T_l)
                if t_l is not None:
                    scanner_accept[s_s2] = t_l
                elif not entry:
                    report_conflict(s_p, s_s2, T_s, t_s, T_l)
            entry.add(s_s2)
            resolve(s_p, s_s2, tuple(sorted(set(T_s + T_l))), t_l)
        indent -= 2
    indent -= 2

def pslr():
    resolve(None, 0, (), None)
    print(scanner_accept)

def main():
    pslr()

if __name__ == '__main__':
    main()
